A computer memory system (or memory, for short) comprises a plurality of memory locations for the storage and retrieval of data. A memory location is the smallest unit of memory that can be individually accessed, using a corresponding address for identification that is unique within the system.
Basic and well-known memory operations include allocating, freeing, reading, writing, and initializing memory locations. Many programs allocate and free memory locations, and most all programs read data from and write data to memory locations.
Many memory operations pertain generally to the process of allocating memory. "Allocation" is the process of making a set of memory locations available to a particular program or procedure. When performed during execution of the program, the operation is called "dynamic allocation." Not all memory areas are typically allocated dynamically; some can be statically allocated with pre-initialization or without initialization (e.g., variables and arrays of fixed size needed during the entire execution of a program); and some (e.g., stack) can be allocated and de-allocated automatically, without explicit request from the program, as procedures are called. "Freeing" is the process of de-allocating locations that were previously allocated, thus permitting them to be allocated for other purposes.
Other types of memory operations pertain to accessing the contents of the memory locations. "Writing" is the process of storing data in memory locations, and "reading" is the process of retrieving data from memory locations. "Initializing" is the process of setting the contents of memory locations to an initial, pre-determined value.
Only a few sequences of these basic memory operations are "valid," i.e., are not regarded as errors or violations. Memory access violations include, for example, allocation violations, read violations, uninitialized memory reads, write violations, and memory freeing errors. To enable an understanding of the invention, these terms can be defined as follows:
An "allocation violation" occurs in the unlikely event that a system attempts to allocate a portion of memory that has been allocated (and not freed) previously. PA1 A "read violation" occurs when a program attempts to read from a memory location that is not allocated for use by that program. PA1 An "uninitialized memory read" occurs when a program attempts to read from a memory location before it is written. PA1 A "write violation" occurs when a program attempts to write to a memory location that is not allocated for use by that program. PA1 A "memory freeing error" occurs, e.g., when a program attempts to free a memory location that is not currently allocated for use by the program.
On the occurrence of any of these violations, the program may obtain incorrect data, i.e., whatever data happens to be stored at the accessed memory location. Consequently, each of these violations can result in faulty program execution, incorrect program results, or complete program failure (often called "system crash").
A programmer can employ known software-based tools for enabling monitoring of memory accesses during run-time of a program to assure validity of memory operations. Use of such tools can be particularly important during debugging of programs written in advanced programming languages such as C/C++, whose programmer-manipulatable pointers can make it difficult to track down memory-access violations.
The software tools available to a programmer include conventional instrumenting programs that can equip a program under development for self-monitoring of memory accesses. The instrumenting program can modify the program code, e.g., at link time, for invoking a routine, e.g., a memory monitoring routine, upon each preselected memory access during run-time of the program.
See, for example, U.S. Pat. No. 5,193,180 (whose disclosure is incorporated herein by reference). See, also, Amitabh Srivastava and Dave W. Wall, "A Practical System for Intermodule Code Optimization at Link-Time," Journal of Programming Languages, March, 1993, (and the same article as published by Digital Equipment Corporation, WRL Research Report 92/6, December 1992), which describes code modification using an intermediate, symbolic language.
After instrumenting, the program under development can monitor its own memory accesses. This is achieved conventionally using a memory status table for maintaining information about the status of memory locations. Typically, the table is stored separately from the memory locations normally available for access by the program.
For example, U.S. Pat. No. 5,193,180 describes a technique by which an executable program can monitor its own memory accesses using a dedicated table that maintains information about three memory states: allocated-and-initialized, allocated-and-uninitialized, and unallocated. According to that patent, the allocated-and-initialized state corresponds to a memory location having been allocated to the program, and initialized by having valid data for the program written thereto. The allocated-and-uninitialized state corresponds to a memory location having been allocated to the program but not initialized. The unallocated state corresponds to a memory location having not been allocated to the program. Using such a table, the memory monitoring routine can signal an error if a memory location having unallocated status is accessed for a write-type operation, or if a memory location having either an unallocated status or an allocated-and-uninitialized status is accessed for a read-type operation. Unfortunately, the technique described in that patent uses a significant amount of memory overhead for that table, and consumes a significant amount of processing time in checking for only read type, uninitialized-memory-read type, and write type violations.
Other, conventional, memory monitoring techniques identify only a single type of violation, e.g., an uninitialized memory read. Examples of such techniques are described in James J. Horning, "What the Compiler Should Tell the User," Compiler Construction, An Advanced Course, Springer-Verlag, 1974, pages 525-548. A first example of such a technique described in the Horning reference associates, during compiling, an extra flag bit with each variable location, indicating whether the variable contains a valid value. (A "variable location" is a memory location whose contents define a variable used in a program.) That technique can then test that value upon each memory reference during run-time. A described alternative technique uses a single value (e.g., the largest negative number) representing each uninitialized variable, which is stored in the variable location. Upon each memory reference to that location, its contents can be tested to determine whether the associated memory location remains uninitialized.
It would be desirable to provide a memory access monitoring technique that can check for a greater range of possible access violations, and can reduce significantly the memory overhead requirements associated with error signalling.